package pers.vic.basics.algorithm.dp;

/**
 * @description:1. 青蛙跳阶梯  动态规划
 * 一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法
 * {@literal https://www.zhihu.com/question/291280715/answer/1570410869}
 * @author Vic.xu
 * @date: 2020/11/12 0012 10:23
 */
public class A_01_frog {
    /*
        利用历史记录，来避免我们的重复计算。
        而这些历史记录，我们得需要一些变量来保存，一般是用一维数组或者二维数组来保存
        1. 定义数组元素的含义
        2. 数组元素之间的关系式: 利用历史数据类推出新的数据，类似归纳法或者递归
        3. 找出初始值，

     */

    /*
    1. 数组的含义 arr[i] 跳上n阶的跳法
    1. 关系：青蛙 跳上n层  可以是n-1 也可以是n-2层跳上来的 f(n) = f(n-1) + f(n-2)
    2. 初始值 f0 = 0， f1=1  f2 = 2
     */
    public static int jump(int n) {
        if (n <= 1) {
            return n;
        }
        int[] dp = new int[n + 1];
        dp[0] = 0;
        dp[1] = 1;
        dp[2] = 2;
        for (int i = 3; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }

    public static int jump2(int n) {
        if (n <= 0) {
            return 0;
        }
        if (n < 3) {
            return n;
        }
        return jump2(n - 1) + jump(n - 2);
    }

    public static void main(String[] args) {
        for (int i = 0; i < 10; i++) {
            System.out.println(i +" -> " +jump(i) + " : " + jump2(i));
        }
    }
}
